#include<iostream>

struct ListNode
{
    int val;
    ListNode* next;
    ListNode():val(0), next(nullptr) {}
    ListNode(int x):val(x), next(nullptr) {}
    ListNode(int x, ListNode* ptr):val(x), next(ptr) {}
};

//f1
ListNode* addTwoNumbers1(ListNode* l1, ListNode* l2) {
    ListNode* result = new ListNode(0);
    ListNode* dummy_node = new ListNode(0, result);

    int l1_val = 0;
    int l2_val = 0;

    while(1)
    {
        if(l1 == nullptr)
        {
            l1_val = 0;
        }
        else
        {
            l1_val = l1->val;
            l1 = l1->next;
        }

        if(l2 == nullptr)
        {
            l2_val = 0;
        }
        else
        {
            l2_val = l2->val;
            l2 = l2->next;
        }

        int sum = l1_val + l2_val + result->val;
        int first = sum % 10;
        int second = sum / 10;
        result->val = first;

        if(second == 1)
        {
            ListNode *tmp = new ListNode(1);
            result->next = tmp;
        }
        else
        {
            if(l1 == nullptr && l2 == nullptr)
            {
                break;
            }
            else
            {
                ListNode *tmp = new ListNode(0);
                result->next = tmp;
            }
        }

        result = result->next;
    }

    return dummy_node->next;
}

//f2
ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2) {
    ListNode* result = new ListNode();
    ListNode* dummy_node = result;

    int second = 0;
    while(second || l1 || l2)
    {         
        if(l1 != nullptr)
        {
            second += l1->val;
            l1 = l1->next;
        }

        if(l2 != nullptr)
        {
            second += l2->val;
            l2 = l2->next;
        }

        result->next = new ListNode(second % 10);
        result = result->next;
        second = second / 10; 
    }

    return dummy_node->next;
}

void OutPutListNodeVal(ListNode *head)
{
    std::cout<<"[";
    ListNode *cur_node = head;
    while (cur_node != nullptr)
    {
        std::cout<<cur_node->val;
        cur_node = cur_node->next;
        if (cur_node != nullptr)
        {
            std::cout<<", ";
        }
    }
    std::cout<<"]."<<std::endl;
}

void TestCase1()
{
    //case 1
    // 输入：l1 = [2,4,3], l2 = [5,6,4]
    // 输出：[7,0,8]
    ListNode *case1_l1_node0 = new ListNode(2);
    ListNode *case1_l1_node1 = new ListNode(4);
    ListNode *case1_l1_node2 = new ListNode(3);
    ListNode *case1_l2_node0 = new ListNode(5);
    ListNode *case1_l2_node1 = new ListNode(6);
    ListNode *case1_l2_node2 = new ListNode(4);

    case1_l1_node0->next = case1_l1_node1;
    case1_l1_node1->next = case1_l1_node2;
    case1_l2_node0->next = case1_l2_node1;
    case1_l2_node1->next = case1_l2_node2;

    ListNode *head = addTwoNumbers1(case1_l1_node0, case1_l2_node0);
    // output
    OutPutListNodeVal(head);
}

void TestCase2()
{
    //case 2
    // 输入：l1 = [0], l2 = [0]
    // 输出：[0]
    ListNode *case1_l1_node0 = new ListNode(0);
    ListNode *case1_l2_node0 = new ListNode(0);

    ListNode *head = addTwoNumbers1(case1_l1_node0, case1_l2_node0);
    // output
    OutPutListNodeVal(head);
}

void TestCase3()
{
    //case 1
    // 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    // 输出：[8,9,9,9,0,0,0,1]
    ListNode *case1_l1_node0 = new ListNode(9);
    ListNode *case1_l1_node1 = new ListNode(9);
    ListNode *case1_l1_node2 = new ListNode(9);
    ListNode *case1_l1_node3 = new ListNode(9);
    ListNode *case1_l1_node4 = new ListNode(9);
    ListNode *case1_l1_node5 = new ListNode(9);
    ListNode *case1_l1_node6 = new ListNode(9);
    ListNode *case1_l2_node0 = new ListNode(9);
    ListNode *case1_l2_node1 = new ListNode(9);
    ListNode *case1_l2_node2 = new ListNode(9);
    ListNode *case1_l2_node3 = new ListNode(9);

    case1_l1_node0->next = case1_l1_node1;
    case1_l1_node1->next = case1_l1_node2;
    case1_l1_node2->next = case1_l1_node3;
    case1_l1_node3->next = case1_l1_node4;
    case1_l1_node4->next = case1_l1_node5;
    case1_l1_node5->next = case1_l1_node6;

    case1_l2_node0->next = case1_l2_node1;
    case1_l2_node1->next = case1_l2_node2;
    case1_l2_node2->next = case1_l2_node3;

    ListNode *head = addTwoNumbers1(case1_l1_node0, case1_l2_node0);
    // output
    OutPutListNodeVal(head);
}

int main()
{
    TestCase1();
    TestCase2();
    TestCase3();
    return 0;
}